#pragma once
#include<iostream>
#include<string>
#include<vector>
using namespace std;

template <class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template <>
struct HashFunc<string>
{
	size_t val = 0;
	size_t operator()(const string& key)
	{
		for (const auto ch : key)
		{
			val *= 131;
			val += ch;
		}
		return val;
	}
};

enum State
{
	EMPTY,
	DELETE,
	EXIST
};

template <class K,class V>
struct HashData
{
	vector<pair<K, V>> _tables;
	State _state = EMPTY;
};

template <class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (Find(kv.first))
			return false;
		if (_tables.size() == 0 || 10 * _size / _tables.size() > 7)
		{
			size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
			HashTable newTables;
			newTables._tables.resize(newSize);
			for (auro& e : _tables)
			{
				if (e._state == EXIST)
				{
					newTables.Insert(e._kv);
				}
			}
			_tables.swap(newTables._tables);
		}
		Hash hash;
		size_t hashi = hash(kv.first) % _tables.size();
		while (_tables[hashi]._state != EMPTY)
		{
			hashi++;
			hashi %= _tables.size();
		}
		_tables[hashi]._kv = kv;
		_tables[hashi]._state = EXIST;
		++_size;
		return true;
	}
	HashData<K, V>* Find(const K& key)
	{
		if (_tables.size() == 0)
			return false;
		Hash hash;
		size_t start = hash(key) % _tables.size();
		size_t hashi = start;
		while (_tables[hashi]._state != EMPTY)
		{
			if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
			{
				return &_tables[hashi];
			}
			hashi++;
			hashi %= _tables.size();
			if (start == hashi)
			{
				break;
			}
		}
		return nullptr;
	}
	bool Erase(const K& key)
	{
		if (_tables.size() == 0)
			return false;
		HashData<K, V>* ret = Find(key);
		if (ret)
		{
			ret->_state = DELETE;
			--_size;
			return true;
		}
		else
		{
			return false;
		}
	}
	void Print()
	{
		for (size_t i = 0; i < _tables.size(); i++)
		{
			if (_tables[i]._state == EXIST)
			{
				cout << _tables[i]._kv.first << endl;
			}
			else
			{
				cout << endl;
			}
		}
	}
private:
	vector<HashData<K, V>> _tables;
	size_t _size = 0;
};

//template <class K>
//struct HashFunc
//{
//	size_t operator()(const K& key)
//	{
//		return (size_t)key;
//	}
//};
//template <>
//struct HashFunc<string>
//{
//	size_t val = 0;
//	size_t operator()(const string& key)
//	{
//		for (const auto ch : key)
//		{
//			val *= 131;
//			val += ch;
//		}
//		return val;
//	}
//};
//enum State
//{
//	EMPTY,
//	DELETE,
//	EXIST
//};
//
//template <class K,class V>
//struct HashData
//{
//	pair<K, V> _kv;
//	State _state = EMPTY;
//};
//
//template <class K,class V,class Hash =HashFunc<K>>
//class HashTable
//{
//public:
//	bool Insert(const pair<K,V> kv)
//	{
//		if (Find(kv.first))
//			return false;
//		if (_tables.size() == 0 || 10 * _size / _tables.size() > 7)
//		{
//			size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
//			HashTable newTables;
//			newTables._tables.resize(newSize);
//			for (auto e : _tables)
//			{
//				if (e._state == EXIST)
//				{
//					newTables.Insert(e._kv);
//				}
//			}
//			_tables.swap(newTables._tables);
//		}
//		Hash hash;
//		size_t hashi = hash(kv.first) % _tables.size();
//		while (_tables[hashi]._state == EXIST)
//		{
//			hashi++;
//			hashi %= _tables.size();
//		}
//		_tables[hashi]._kv = kv;
//		_tables[hashi]._state = EXIST;
//		++_size;
//		return true;
//	}
//	HashData<K, V>* Find(const K& key)
//	{
//		if (_tables.size() == 0)
//			return nullptr;
//		Hash hash;
//		size_t start = hash(key) % _tables.size();
//		size_t hashi = start;
//		while (_tables[hashi]._state != EMPTY)
//		{
//			if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
//			{
//				return &_tables[hashi];
//			}
//			hashi++;
//			hashi %= _tables.size();
//			if (start == hashi)
//			{
//				break;
//			}
//		}
//		return nullptr;
//	}
//	bool Erase(const K& key)
//	{
//		HashData<K, V>* ret = Find(key);
//		if (ret)
//		{
//			ret->_state = DELETE;
//			--_size;
//			return true;
//		}
//		else
//		{
//			return false;
//		}
//	}
//	void Print()
//	{
//		for (size_t i = 0; i < _tables.size(); i++)
//		{
//			if (_tables[i]._state == EXIST)
//			{
//				printf("[%d:%d] ", i, _tables[i]._kv.second);
//			}
//			else
//			{
//				printf("[%d:*] ", i);
//			}
//		}
//		cout << endl;
//	}
//private:
//	vector<HashData<K, V>> _tables;
//	size_t _size = 0;
//};